package year2024.month4;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class ClimbStairs {

    @Test
    void test1() {
        Assertions.assertEquals(2, climbStairs(2));
    }

    @Test
    void test2() {
        Assertions.assertEquals(3, climbStairs(3));
    }

   /* @Test
    void test3(){
        Assertions.assertEquals(2,climbStairs(2));
    }*/

    /**
     * 70 爬楼梯
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * <p>
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        stairsMethods = new int[n + 1];
        Arrays.fill(stairsMethods, -1);

        return calculate(n);
    }

    int[] stairsMethods;

    public int calculate(int n) {
        int stairsMethod = stairsMethods[n];
        if (stairsMethod != -1) {
            System.out.println("爬" + n + "级台阶，有" + stairsMethod + "种方法");

            return stairsMethod;
        }

        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        }

        int result = calculate(n - 1) + calculate(n - 2);
        return stairsMethods[n] = result;
    }
}
